#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

#include <limits.h>
using namespace std;


//refer to mit handout
//http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf

double findKthHelper(vector<int> A, vector<int> B, int left, int right, int m, int n, int k)
{
    if (left > right)
        return findKthHelper(B, A, 0, min(k,n), n, m, k);

    int indexA = (left+right)/2;
    int indexB = k - indexA;
    if (A[indexA-1] >= B[indexB-1]&& A[indexA-1] <= B[indexB]) {
        return A[indexA-1];
    } else if (A[indexA-1] < B[indexB-1] || indexB > n) {
        //cout << "Jump to here" << endl;
        return findKthHelper(A, B, indexA + 1, right, m, n, k);
    } else {
        return findKthHelper(A, B, left, indexA -1, m, n, k);
    }
}

class Solution {
    public:
        double findKthSortedArrays(int A[], int m, int B[], int n, int k) {
            if (k == 0) return min(A[0], B[0]);
            if (k == m+n-1) return max(A[m-1], B[n-1]); 
            if (m == 0 ) return B[k-1];
            if (n == 0) return A[k-1];
            if (m > n) return findKthSortedArrays(B, n, A, m, k);
            vector<int> Avec, Bvec;
            Avec.push_back(INT_MIN);
            Bvec.push_back(INT_MIN);
            for (int i = 0; i < m; i++)
                Avec.push_back(A[i]);
            for (int i = 0; i < n; i++)
                Bvec.push_back(B[i]);
            Avec.push_back(INT_MAX);
            Bvec.push_back(INT_MAX);
            m += 2;
            n += 2;
            k+= 2;
            return findKthHelper(Avec, Bvec, 1, min(m,k), m, n, k);

        }
};

int main(int argc, char **argv)
{
    Solution mySolution;


    cout << "-----------------Test 1--------------------" << endl;
    int A1[] = {1,3,4};
    int B1[]= {2,5,6,8,9,10};
    double result = mySolution.findKthSortedArrays(A1, sizeof(A1)/sizeof(int), B1, sizeof(B1)/sizeof(int), 9);
    cout << result << endl;

    cout << "-----------------Test 2--------------------" << endl;
    int A2[] = {1,3,4,7};
    int B2[]= {2,5,6,8,9,10};
    double result1 = mySolution.findKthSortedArrays(A2, sizeof(A2)/sizeof(int), B2, sizeof(B2)/sizeof(int), 5);
    cout << result1 << endl;

    cout << "-----------------Test 3--------------------" << endl;
    int A3[] = {1,2,3};
    int B3[]= {1,2};
    double result3 = mySolution.findKthSortedArrays(A3, sizeof(A3)/sizeof(int), B3, sizeof(B3)/sizeof(int), 2);
    cout << result3 << endl;

    cout << "-----------------Test 4--------------------" << endl;
    int A4[] = {};
    int B4[]= {2,5,6,8,9,10};
    double result4 = mySolution.findKthSortedArrays(A4, sizeof(A4)/sizeof(int), B4, sizeof(B4)/sizeof(int), 3);
    cout << result4 << endl;


    cout << "-----------------Test 5--------------------" << endl;

}
